package com.lw.leetcode.str.b;

import java.util.ArrayList;
import java.util.List;

/**
 * create by idea
 * 438. 找到字符串中所有字母异位词
 * 剑指 Offer II 015. 字符串中的所有变位词
 *
 * @author lmx
 * @version 1.0
 * @date 2021/11/28 19:10
 */
public class FindAnagrams {


    public static void main(String[] args) {
        FindAnagrams test = new FindAnagrams();

        // []
//        String str = "aa";
//        String str1 = "bb";
        // []
        String str = "aaaaaaaaaa";
        String str1 = "aaaaaaaaaaaaa";


        List<Integer> anagrams = test.findAnagrams(str, str1);
        System.out.println(anagrams);
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int length = p.length();
        int len = s.length();
        if (len < length) {
            return list;
        }
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];
        char[] arr = s.toCharArray();
        for (int i = 0; i < length; i++) {
            arr1[p.charAt(i) - 'a']++;
            arr2[arr[i] - 'a']++;
        }
        boolean flag = true;
        for (int k = 0; k < 26; k++) {
            if (arr1[k] != arr2[k]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            list.add(0);
        }
        int j = length;
        int i = 0;
        while (j < len) {
            arr2[arr[j++] - 'a']++;
            arr2[arr[i++] - 'a']--;
            flag = true;
            for (int k = 0; k < 26; k++) {
                if (arr1[k] != arr2[k]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                list.add(i);
            }
        }
        return list;
    }

}
